For electrically processing an image related data, the data is converted into a code to be recognized by a machine, such as a computer. For transmitting an image data via telephone line, radio waves, or the like, the image data is generally compressed to reduce the amount of data to be transmitted.
In practice, an image data supplied from an image information source is encoded by an encoder in a transmitter to compress the image data. The encoded signal is decoded by a decoder in the receiver to reproduce the original image data. In some cases, a plurality of conversion parameters are used for encoding and decoding processes. In this kind of conversion process, an adaptive conversion technique may be used, in which the conversion parameter is updated in accordance with statistical characteristics of the image data to improve the efficiency of the conversion (compressing ratio).
A conventional image data encoding apparatus, which uses the adaptive arithmetic encoding technique, includes a symbol sequence reader which reads an input image data as a binary symbol sequence; a symbol sequence buffer which stores the binary symbol sequence; and a reference symbol selector. The reference symbol selector selects a symbol pattern, which is the most closely correlated to the current symbol, from the binary symbol sequence. Such a symbol pattern is hereinafter called template. The encoding apparatus further includes a state number/MPS memory and a prediction conversion unit. "MPS" is an abbreviation of more probable symbol, which is a prediction value to the current symbol. The prediction conversion unit finds whether or not the current symbol is identical to its more probable symbol MPS stored in the state number/MPS memory. The state number represents the status of the corresponding context.
The encoding apparatus further includes a probability estimation table which store, for each state number, a probability interval (LSZ) of a less probable symbol LPS and transition information of the state number ST. The less probable symbol LPS is determined opposite to the more probable symbol MPS for each state number. The encoding apparatus further includes an arithmetic encoder which arithmetically encodes the current symbol in accordance with the output of the prediction conversion unit, the state number ST and the more probable symbol MPS, the probability interval LSZ and the transition state.
According to the above-described conventional encoding apparatus, many processes are required for encoding each symbol, such as searching the state number/MPS memory, searching the probability estimation table, performing prediction conversion process, calculating the probability interval, etc. Consequently, it is difficult to improve the encoding speed.
For solving the above-mentioned problems, some inventions are proposed in Japanese Patent Laying Open, Kokai No. H5-67978. One invention described in the publication, hereinafter called invention (1), includes a random-access memory storing a state number and a more probable symbol MPS for each context, a detector detecting whether the current context is identical to specific one or more than one other contexts, at least one register which stores the state number and the more probable symbol MPS for the specific context(s), and a selector which selects one from two outputs of the memory and the register(s) in response to the output of the detector.
If the current context is in a specific condition, the selector selects the register(s) not the memory to obtain the state number and the more probable symbol MPS for the current context. In the other cases, the selector selects the memory to obtain the state number and the more probable symbol MPS for the current context. As a result, encoding and decoding speed may be improved relative to the before mentioned conventional encoding (decoding) apparatus.
Another invention described in the above-mentioned publication, hereinafter called invention (2), includes a random-access memory storing a state number and a more probable symbol MPS for each context; a rester which stores the state number and the more probable symbol MPS for the current symbol, just read from the memory, or updated state number and more probable symbol MPS for the last context; and a control circuit which decides whether or not the current symbol is identical to a predicted value and updates the state number and the more probable symbol MPS in the memory in accordance with its decision. The apparatus further includes a detector which detects whether or not the context for the current symbol is identical to the last context and updates the register in accordance with the detecting result; and an arithmetic encoder which encodes the current symbol in accordance with the state number and more probable symbol MPS, supplied from the register.
In accordance with the decision of the control circuit, the updated state number and more probable symbol MPS for the last symbol and the sate number and the more probable symbol MPS outputted from the memory are selectively used for encoding process. Consequently, the state number and more probable symbol MPS of the next symbol can be searched while performing arithmetic operation for the current symbol, and therefore, encoding and decoding speed improves.
In general, an encoding apparatus is designed to manage various kinds of image data including, for instance, a text image, error diffusion image, and multi-level image with lower and upper bit-planes. According to the invention (1) disclosed in Japanese Patent Laying Open, Kokai, No. H5-67978, however, it is difficult to estimate a more probable context. As a result, the encoding and decoding speed is not remarkably improved when processing the various kinds of image data.
According to the invention (2), arithmetic operation is performed for a plurality of symbols simultaneously when the same contexts are inputted successively to improve encoding and decoding speed. However, it is difficult to estimate a more probable context as well as the invention (1). Even if such a more probable context can be estimated accurately, state transition process must be performed very often for each context in the case where the memory is updated very often. And therefore, the state number and the more probable symbol MPS for each context must be updated many times. Consequently, the encoding and decoding speed may not he improved remarkably when processing various kind of image data.
In addition, improvement of encoding and decoding speed is limited in the adaptive arithmetic encoding process. That is because, the interval calculation on the real-number line for the current symbol includes the search of the interval width table (access to the probability estimation table); (reverse) prediction conversion process; interval calculation; update of an interval register; calculation of the lower bound of a code register; and update of the code register. Such process generally takes much longer time than that for searching the state number and more probable symbol of the next symbol, therefore, the cycle of the system clock is defined by the interval calculation on the real-number line for the current symbol. As a result, it is difficult to improve the speed of encoding process as a whole.